package com.javabase.y2022.m05.day0516.v01;


import java.util.ArrayList;

/**
 * @descriptions: Solution
 * @author: Tom
 * @date: 2022/5/16 上午 11:11
 * @version: 1.0
 */
public class Solution {
    public static void main(String[] args) {
        TreeNode root = new Solution().new TreeNode(2);
        root.left = new Solution().new TreeNode(5);
        root.right = new Solution().new TreeNode(3);
        TreeNode p = new Solution().new TreeNode(1);
        TreeNode ans = new Solution().inorderSuccessor(root, p);
        if(ans != null){
            System.out.println(ans.val);
        } else {
            System.out.println("NULL");
        }

    }

    // 设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
    //如果指定节点没有对应的“下一个”节点，则返回null。
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null) {
            return null;
        }
        ArrayList<TreeNode> list = new ArrayList<>();
        list = in(root, list);
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).val == p.val && i < list.size() - 1) {
                return list.get(i + 1);
            }
        }
        return null;
    }

    public ArrayList<TreeNode> in(TreeNode head, ArrayList<TreeNode> list) {
        if (head.left != null) {
            in(head.left, list);
        }
        list.add(head);
        if (head.right != null) {
            in(head.right, list);
        }
        return list;
    }
}















